package 字符串;


import java.util.HashMap;
/**
 * @author: 大怪
 * @email: 962527441@qq.com
 */

/**
 * 题目：
 * 给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。
 * 如果 s 中存在多个符合条件的子字符串，返回任意一个。
 * 注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 *
 * 示例 1：
 *
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'
 *
 */
public class 含有所有字符的最短字符串 {
    class Solution {
        public String minWindow(String s, String t) {
            HashMap<Character, Integer> map1 = new HashMap<Character, Integer>();
            HashMap<Character, Integer> map2 = new HashMap<Character, Integer>();
            for (int i = 0; i < t.length(); i++) {
                char c = t.charAt(i);
                map1.put(c, map1.getOrDefault(c, 0)+1);
            }
            int len = Integer.MAX_VALUE;
            int left = 0;
            int right = 0;
            int count = 0;
            int min = 0;
            for (int i = 0; i < s.length(); i++) {
                char c =s.charAt(i);
                right++;
                if (map1.containsKey(c)) {
                    map2.put(c,map2.getOrDefault(c, 0)+1);
                    if (map1.get(c).equals(map2.get(c))) {
                        count++;
                    }
                }
                while(count == map1.size()) {
                    if (right-left<len) {
                        min = left;
                        len = right-left;
                    }
                    char b = s.charAt(left);
                    left++;
                    if (map1.containsKey(b)) {
                        if (map1.get(b).equals(map2.get(b))) {
                            count--;
                        }
                        map2.put(b,map2.getOrDefault(b, 0)-1);
                    }
                }
            }
            return len == Integer.MAX_VALUE? "":s.substring(min,min+len);
        }
    }
}
